package codeTop;

import java.util.List;

public class q234 {
    public boolean isPalindrome(ListNode head) {
        ListNode p = head;
        ListNode mid = findMid(head);
        mid.next = reverse(mid.next);
        mid = mid.next;
        while (mid != null) {
            if (p.val != mid.val) {
                return false;
            }
            mid = mid.next;
            p = p.next;
        }
        return true;
    }
    ListNode findMid(ListNode node){
        ListNode head = new ListNode();
        head.next = node;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null&&fast.next!=null) {
            fast= fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    ListNode reverse(ListNode node){
        if (node == null) {
            return null;
        }
        ListNode p = node;
        ListNode next = p.next;
        p.next = null;
        while (next != null) {
            ListNode temp = next.next;
            next.next = p;
            p = next;
            next = temp;
        }
        return p;
    }

    public static void main(String[] args) {
        q234 q = new q234();
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        System.out.println(q.isPalindrome(node));
    }
}
